package pro.softzhang.algo.lc0;

import pro.softzhang.algo.flag.knowledge.KBinarySearch;

/**
 * 35. 搜索插入位置
 * https://leetcode.cn/problems/search-insert-position
 */
public class LC35_SearchInsertPosition {
    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6};
        int target = 5;
        int idx = new Solution().searchInsert(nums, target);
        System.out.println(idx);
    }
    
    @KBinarySearch
    static
    class Solution {
        public int searchInsert(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int middle = (left + right) / 2;
                if(nums[middle] >= target) {
                    if(middle == 0 || nums[middle - 1] < target) {
                        return middle;
                    }
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            }
            return nums.length;
        }
    }
}